let direction = [
    [-1, 0],
    [1, 0],
    [0, 1],
    [0, -1]
];
var minimumObstacles = function(grid) {
    let deleteObstacle = new Array();
    let imax = grid.length;
    let jmax = grid[0].length;
    let visited = new Array(imax).fill().map(() => new Array(jmax).fill(false));
    let ans = 0;
    let arr = new Array;
    while (!bfs(grid, arr, imax - 1, jmax - 1)) {
        for (let i = 0; i < deleteObstacle.length; i++) {
            let [m, n] = deleteObstacle[i];
            arr.push([m, n]);
            grid[m][n] = 0;
        }
        ans++;
        deleteObstacle = new Array();
    };
    // console.log(bfs(grid,deleteObstacle,0,0,imax-1,jmax-1))
    return ans;

    function bfs(grid, arr, x, y) {
        if (arr.length == 0) {
            arr.push([0, 0]);
        }
        while (arr.length > 0) {
            let [i1, j1] = arr.shift();
            if (i1 == x && j1 == y) return true;
            for (let k = 0; k < 4; k++) {
                let [dx, dy] = direction[k];
                if (i1 + dx >= 0 && i1 + dx < imax && j1 + dy >= 0 && j1 + dy < jmax && !visited[i1 + dx][j1 + dy]) {
                    if (grid[i1 + dx][j1 + dy] == 0) {
                        if (i1 + dx == x && j1 + dy == y) return true;
                        arr.push([i1 + dx, j1 + dy]);
                    } else {
                        deleteObstacle.push([i1 + dx, j1 + dy]);
                    }
                    visited[i1 + dx][j1 + dy] = true;
                }
            }
        }
        return false;
    }
};

let grid = [
    [0, 1, 1],
    [1, 1, 0],
    [1, 1, 0]
];
console.log(minimumObstacles(grid));